\chapter{Implementation of prototype}
This chapter describes the implementation of our prototype in CoreCalc. We describe the implementation of the approaches described in chapter \ref{possibilities} and the problems and limitations of the design. 

\section{Built-in functions} %---------------------------------------------------------------------------------------------------------------------

As described in chapter \ref{possibilities}, formulas can invoke functions. For example $=SIN(90)$ is a formula that invokes the sinus function and $=A1+20$ invokes the add function. We have chosen to implement a small range of these functions that showed potential to be performance wise better on the GPU. 

In CoreCalc, a spreadsheet function is represented as an object of the class \keyword{Function}. \keyword{Function} connects the function name, represented as a string, and a delegate called an \keyword{Applier} which points to the function.

\begin{lstlisting}[caption=Applier,label=code:applier, language=CSharp]
delegate Value Applier(Sheet sheet, Expr[] es, int col, int row);
\end{lstlisting}

A functions applier is invoked when a function is called from a specific Cell.  We would like to benchmark the current CPU implementation in CoreCalc against the calculations on the GPU, therefore we need both a GPU-Applier and CPU-Applier, for a single function.

This simple design allows us to easily choose between GPU and CPU Appliers by simply changing the target platform on the function class.
\begin{lstlisting}[caption=GPU and CPU applier,label=code:cpu+gpu applier, language=CSharp]
class Function {
    public enum TargetPlatform { CPU, GPU }
    public static TargetPlatform target;

	private Applier applierCPU;
	private Applier applierGPU;
	
    public Applier Applier
    {
        get {
			return applierGPU == null || target == TargetPlatform.CPU ? applierCPU : applierGPU;
		}
		...
	}
	...
}	
\end{lstlisting}

Because of the static \keyword{TargetPlatform} in the \keyword{Function} class, this implementation does not allow us to make an adaptive implementation where the chosen target is based on the context of the invocation, however it should be possible to choose target platform based on an estimated execution time (described in chapter \ref{possibilities}). However, in the current design of CoreCalc, Appliers are simply returned when a function is called, and this Applier is called by the callee. This means context is only available outside the function class, or inside the implemented Appliers. Because of this the function being evaluated has to either choose platform, or the choice have to be moved. We have not looked further into this as very few of the built-in function are potentially faster on the GPU. 

By overloading the constructor of the \keyword{Function} class, it is now easy to tie two appliers to a \keyword{Function} by simply changing:

\begin{lstlisting}[caption=Original code for creating MMULT,label=code:, language=CSharp]
new Function("MMULT",
	MakeFunction((Fun<Value[], Value>)MMult));
\end{lstlisting}

into:

\begin{lstlisting}[caption=Modified code for creating MMULT,label=code:, language=CSharp]
new Function("MMULT",
	MakeFunction((Fun<Value[], Value>)MMult), 
	  MakeFunction((Fun<Value[], Value>)MMultGPU));
\end{lstlisting}

\section{Sheet defined function} %-----------------------------------------------------------
Sheet defined functions are functions defined within a spreadsheet. A sheet defined function is defined by input cells and an output cell. 

In our tests we found that due to extra latency of transferring data to the GPU, a certain complexity in the operation and a certain amount of data is needed. Sheet defined functions solves the problem of complex operation by allowing the user to define new function using many simple functions. 

To execute a sheet defined function in Accelerator, our goal must be to build Accelerator Expression Graph (AEG) that corresponds to the function. Accelerator does not support inserting values inside an AEG. This means we need to build the AEG when all values of the function, parameters included, are known.

Because of this we introduce a middle layer, Accelerator Abstract Syntax (AAS), that will quickly be able to build an AEG given parameters. The details of this will be discussed below.

\subsection{Accelerator Abstract Syntax} %---------------------------------------
The base for AAS is the abstract class \keyword{AccExpr}:

\begin{lstlisting}[caption=AccExpr class,label=code:, language=CSharp]
public abstract class AccExpr
{
	public abstract FPA GenerateFPA(AccInputInfo info, int CallID);
}
\end{lstlisting}

A reference to the root \keyword{AccExpr} of a SDF is placed along with the compiled SDF. On evaluation time, this AccExpr's GenerateFPA-method will be called with the parameters, the AEG will be generated, and it will be executed on the GPU and the result returned.

\begin{figure}[H]
\includegraphics[width=1.0\textwidth]{pics/expr-diagram.png}
\caption{Class hierarchy of Expr types\cite{sestoft}}
\label{expr class hierarchy}
\end{figure}

\begin{figure}[H]
\includegraphics[width=1.0\textwidth]{pics/accExpr-diagram.png}
\caption{Class hierarchy of AccExpr}
\label{accexpr class hierarchy}
\end{figure}

In CoreCalc, whenever a cell is changed the string in the cell is parsed and a Expr-AST (See fig. \ref{expr class hierarchy}) is build.   CoreCalc SDFs are compiled into .NET bytecode.  Before compilation, the functions Expr-AST is translated into a CGExpr abstract syntax. This is achieved with a Visitor-pattern that visits all child expressions and translates them individually. 

Converting Expr abstract syntax (\ref{expr class hierarchy}) into AASs will be done the same way - creating a concrete visitor that visits all leaves in an Expr node, and translate them. Some operations possible in CoreCalc will not be possible in Accelerator, if these are encountered, an exception is thrown. We will not handle these cases in this project.

CoreCalc expressions can be of the following types: NumberConst, TextConst, Error, FunCall, CellRef, CellArea. We will now look into how translation of these will work.

\subsubsection{Values}
All number values have to be represented as FPAs in Accelerator, we work with conversion of NumberConsts, CellRefs, and CellAreas from CoreCalc into FPAs. Input arguments will have to be represented as FPAs as well, but we discuss this later. NumberConsts (Constants in formulas such $2+2$) and NumberCells inside the function sheet is known compiletime and can be represented as AccConst, while CellRefs and CellAreas, if pointing outside the functionsheet, needs to be evaluated at evaluation time and are represented by their own types, AccCellRef and AccCellArea. 

\subsubsubsection{Representation of numbers} %---------------------------------------
\keyword{AccNumber} allows for creating a FPA with the same size as the other argument in the operation it is being used. The argument will typically only be a single float when calling the SDF alone, but as we describe in section {\ref{higher order functions} this is often not the case. 

\begin{lstlisting}[caption=AccNumber class,label=code:, language=CSharp]
public abstract class AccNumber : AccExpr
{
...
protected override FPA GenerateFPA(AccInputInfo info, int CallID)
{
	return new FPA(Value, info.Values[0].GetLength(0), info.Values[0].GetLength(1));
}
...
}
\end{lstlisting}

As both AccCellRef and AccConst inherit from AccNumber they only need to define how to return the value and AccNumber will convert it to an FPA of the correct size as shown above.


\subsubsubsection{Input cells}
Input arguments are CellRef's in the Expr tree, but at compile time we match the CellRef with the list of input cells for the SDF and represent the input of the type \keyword{AccInput} giving the index of the input cell as argument. The input arguments are not known before evaluation time and are send through every GenerateFPA call in the \keyword{AccInputInfo} object. How this is built is explained in section \ref{higher order functions} because it's highly dependent on how the function is called. The AccInput just return the value that corresponds with its index.

\begin{lstlisting}[caption=Generate FPA for AccInput,label=code:, language=CSharp]
protected override FPA GenerateFPA(AccInputInfo info, int CallID)
{ 
	return new FPA(info.Values[inputIndex]);
}
\end{lstlisting}

A general problem when using Accelerator in CoreCalc is that every value in CoreCalc will have to casted to a float, send to the GPU, castet to a double and wrapped in a NumberValue Object. The NumberValue wrapping/unwrapping is however also an issue in SDFs compiled to .NET bytecode. (See Known Problems.)

\subsubsection{Function calls} %---------------------------------------------------------------------------------------------------------------
In Expr syntax, function calls are represented by FunCall. This includes both calls to built-in functions such as $SIN$ and operators such as $+$. These are refined to a whole hierarchy in the CgExpr syntax. Most functions such as $+$ and $SIN$ will easily be translated to Accelerator and is represented in \keyword{AccBinaryOp} or \keyword{AccUnaryOp}, specifying which function in the constructor. Others functions such as comparison and conditional functions that are very simple in CoreCalc will have to be refined similar to how it is done in \keyword{CGExpr}. (Functions that only depends on \keyword{AccConst}s could themselves be represented as an \keyword{AccConst}, but as this is only optimize SDF's if they're poorly designed we have not implemented this.)


\subsubsubsection{Conditional Statements} %-------------------------------------------------------------------------------------------------------
Expr doesn't represent boolean expressions separately, however conditional statements in Accelerator require that we generate boolean expressions. In CoreCalc any value can always be evaluated to true or false, while floats in accelerator never can. Just as the IL code generator for SDFs have conditional expressions that requires functions to return booleans, Accelerator have special functions for comparison of float values, which return arrays of booleans.

In CGExpr conditional statements are represented by CGIF, CGAnd, CGOR, CGNOT and a range of different comparisons inheriting from CGComparison. Due to the scope of our project we have chosen a simple approach where comparison functions are contained to conditional functions where they are needed (see example below). This approach restricts our use of logical operators, but as this is an experimental prototype this is not a problem. We have also chosen not to implement $NOT$, $AND$ and $OR$, due to the scope of the project.

\begin{lstlisting}[caption=GenerateBPA of AccComp ,label=code:, language=CSharp]
public BPA GenerateBPA(AccInputInfo info, int CallID)
{   ...
	switch(type) {
		case Type.EQ:
			return PA.CompareEqual(child1Fpa, child2Fpa);
		case Type.GT:
			return PA.CompareGreater(child1Fpa, child2Fpa);
		...
	}
	...
}
\end{lstlisting}

\subsubsubsection{Random numbers} %---------------------------------------
Accelerator has no volatile methods such as random number generation. Monte Carlo simulations however use a lot of random data and we therefore need to generate it on the CPU at evaluation time. As random numbers are the only volatile function we need within the scope of the project we have contained this to \keyword{AccRand}, that works similar to \keyword{AccNumber}, but generate an array of random numbers corresponding to the size of the other argument in the operation it is being used. This size is available in the AccInputInfo object.

\subsubsection{Ensuring reuse of AccExprs} %---------------------------------------
Because of the latency of transferring data to the GPU it is important that we generate as small an AEG as possible. In order to do this we need to make sure that the AAS doesn't contain the same node more than once. Many cells can have formulas that reference to the same input cell or numbercell. Every reference to the same cell should point to the same AAS object. This means that when creating ASS it's important to keep track of whether an AAS for the same Expr has earlier been created. If it has, this earlier object should be referenced, instead of creating a new instance. 

In order to achieve this we create a dictionary that allows lookups of AccExpr's from a cell address inside the already created Visitor-pattern. Another, and maybe performance wise faster solution, would be to have a Cell (or a decorator) to reference to its AccExpr. However as this is on compile time we haven't looked further into optimizations.

Whenever a AAS translation is starting, a dictionary will be created, and whenever a new Expr is needed we check if it's already has a corresponding AccExpr. Because we haven't focused on optimizing the generation of AAS and because a CellRef pointing to an input cell can be represented by the same AccInput object we simply create the AccExpr object and let the TryAccExpr throw it away if it's not needed.

\begin{lstlisting}[caption=Method for minimizing count of created AccExpr objects  ,label=code:, language=CSharp]
private static AccExpr TryAccExpr(FullCellAddr addr, AccExpr newExpr) 
{
	if(exprCache.ContainsValue(newExpr))
		return newExpr;
	AccExpr n;
	if (!exprCache.TryGetValue(addr, out n))
		n = newExpr;
		exprCache.Add(addr, n);
	}
	return n;
}
\end{lstlisting}

Due to the high transfer latency we have a similar dictionary for number constants. If A1 contains the formula $=2+C1$ and B1 have the formula $=C1/2$, both of these constants would normally have to be transferred to the GPU as separate textures, but we make sure that they point to the same AccConst.

For these optimizations to work on evaluation time the same AAS object should return the same FPA object for each reference in the SDF invocation. To achieve this, we simply make sure that a generated FPA is saved in the AccExpr for each invocation of the SDF (it's only invoked once in a tabulate call. See section \ref{higher order functions}).

FPAs should of course not be shared between invocations and to ensure this we send a unique CallId through the callstack. The only public method of an AccExpr that returns a FPA object is the GenerateFPAWithCache of the abstract class AccExpr that all others inherit from. This method checks if we have already generated a FPA for the AccExpr in this invocation and return the cached FPA, if not it call the objects specific GenerateFPA method. 


\subsection{Higher order functions} %---------------------------------------
\label{higher order functions}
As discussed in chapter \ref{possibilities} using sheet defined function in higher order functions such as \keyword{Map} or \keyword{Tabulate} should improve the potential performance gain if send as one call to the GPU. 

\begin{lstlisting}[caption=Original CoreCalc code for Tabulate ,label=org. tabulate, language=CSharp]
public static Value Tabulate(Value v0, Value v1, Value v2)
{
	if (v0 is FunctionValue && v1 is NumberValue && v2 is NumberValue)
	{
	FunctionValue fv = v0 as FunctionValue;
	//(... Argument error handling ..)
	int rows = (int)(v1 as NumberValue).value,
		cols = (int)(v2 as NumberValue).value;
	if (0 <= rows && 0 <= cols)
	{
		Value[,] result = new Value[cols, rows];
		for (int c = 0; c < cols; c++)
			for (int r = 0; r < rows; r++)
				result[c, r] = fv.Call2(NumberValue.Make(r + 1), NumberValue.Make(c + 1));
	return new ArrayExplicit(result);
	}
	//(... Error handling ..)
}
\end{lstlisting}


The built-in Tabulate function works by taking a binary function and two numbers as arguments. The function is then called $row * col$ times taking $row index$ and $col index$ as argument 1 and 2, respectively. \keyword{Map}, \keyword{ColMap} and \keyword{RowMap} works similar to \keyword{Tabulate}, but takes a \keyword{CellArea} as input and passes the contents of the cells as arguments to the function. We've chosen to explain \keyword{Tabulate} here for simplicity, but the other implementations are similar.
As shown in the code sample \keyword{Tabulate} is implemented with a nested loop calling the method once per argument combination. As this is an embarrassingly parallel problem that can be handled by the GPU we need to represent it as one Accelerator abstract syntax graph. As Accelerator handles each element independently all we have to do is generate a \keyword{FPA} corresponding to the input array before sending it to the GPU. This only requires a minor modification of \keyword{AccExpr}s such as InputAccNod, ConstAccExpr, and RandAccExpr as they have to fit the input.

As described a Sheet defined Function has an \keyword{AccExpr} structure which has a \keyword{FPA GenerateFPA(AccIntputInfo info, int CallID)} method that generates the Accelerator abstract syntax graph that corresponds to the operation based on input arguments. 

\begin{table}[H]
\begin{center} 
\subfloat[Argument 1]{      
\begin{tabular}{| l  | c | c | c | c | c | c | r |} \hline 
 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline 
 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\\ \hline 
\end{tabular} 
}
\subfloat[Argument 2]{
\begin{tabular}{| l  | c | c | c | c | c | c | r |} \hline 
 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline 
 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline 
\end{tabular} 
}
\caption{Original input arguments for call: $TABULATE(F,2,8)$}
\label{table:tabinput1}
\end{center}
\end{table}

\begin{table}[H]
\begin{center} 
\subfloat[Argument 1]{      
\begin{tabular}{| l  | c | c | r |} \hline 
 1 & 1 & 1 & 1 \\ \hline 
 1 & 1 & 1 & 1 \\ \hline
 2 & 2 & 2 & 2 \\ \hline 
 2 & 2 & 2 & 2\\ \hline 
\end{tabular} 
}
\subfloat[Argument 2]{
\begin{tabular}{| l | c | c | r |} \hline 
 1 & 2 & 3 & 4 \\ \hline 
 5 & 6 & 7 & 8 \\ \hline 
 1 & 2 & 3 & 4 \\ \hline 
 5 & 6 & 7 & 8 \\ \hline 
\end{tabular} 
}
\caption{Reorganized input arguments for call: $TABULATE(F,2,8)$}
\label{table:tabinput2}
\end{center}
\end{table}

It is possible to generate an AAS using the first of the above formats table (\ref{table:tabinput1}), but as the data has to be transferred as a texture this format exceeds the maximum texture width or height long before the actual memory limits of the GPU (Maximum texture size of GT240 have been estimated to 4000 X 8000). 
To solve this we reorganize the data to fit the texture size as shown in table \ref{table:tabinput2}. This is done using the \keyword{GenerateAcceleratorMethod} method of \keyword{CGManager.cs}. 

\begin{lstlisting}[caption=Original CoreCalc code for Tabulate, label=code:factorize, language=CSharp]
int cols = (int)Math.Ceiling(Math.Sqrt(length));
while (length % cols != 0)
	cols--;
int rows = length / cols;
\end{lstlisting}

First we find the new format using the algorithm shown in fig. \ref{code:factorize}, where we consider that our tests showed that the texture width was exceeded before the height. We then reorganize the input into the \keyword{ArrayList$<$float[,]$>$} type (each \keyword{float$[,]$} is the reorganized input arguments). This FPA is send to the GPU and the result is reorganized back into the original format before returning the value. This is done completely transparent to the \keyword{Tabulate} or \keyword{Map} function. Another solution would be to do some initial tests and know the maximum texture size of the current machine and simply wrap around the maximum texturewidth.

This solution makes us able to use data sizes close to the maximum texture size, but if we exceeds the maximum texture size the data will have to be split in two. As the operations are data-parallel and element wise when calling sheet defined functions it doesn't matter how the data is partitioned. We haven't implemented this in our prototype (see Future work).

\subsection{Evaluation leafs on the CPU} %---------------------------------------
Expr contains a lot of things that we cannot or have not translated to AAS. A simple approach would be to just evaluate these expressions on the CPU using the normal evaluation in CoreCalc, but this would lead to potential recursive calls to the same version and introduce further uncertainties. Even though this is very simple to implement, we've chosen not to and simply throw and exception if an expression cannot be translated fully.